package arithmetic;

import org.junit.jupiter.api.Test;

import java.util.Objects;

/**
 * 最长公共前缀
 *
 * @author gaojie
 * @date 2022-02-22
 */
public class LongestCommonPrefix {

    @Test
    void test() {
        assert fun(new String[]{"abc", "abd", "abe"}).equals("ab");
        assert fun(new String[]{"abcdefghjkk", "abcdefghjk", "abcdefghj123", "abcdefghj1236"}).equals("abcdefghj");
        assert fun(new String[]{"abc", "1abd", "2abe"}).equals("");
    }

    /**
     * 1.若数组为空，则返回 ""
     * 2.既然是公共前缀，那么每个成员都包含，所以随便取一个就开始比较
     * 3.只要有一个不符合，就将公共前缀缩短 1 位，然后继续比较
     * 4.若公共前缀变为 [""]，那么结束流程
     */
    private String fun(String[] strings) {
        if (strings.length == 0) return "";
        String prefix = strings[0];
        System.out.printf("prefix: [%s]%n", prefix);
        for (String string : strings) {
            while (!string.startsWith(prefix)) {
                prefix = prefix.substring(0, prefix.length() - 1);
                System.out.printf("prefix: [%s]%n", prefix);
            }
            if (Objects.equals(prefix, "")) break;
        }
        System.out.println("----------------------------------------------");
        return prefix;
    }
}
